The invention relates generally to destaging operations in data storage systems.
Mass storage systems typically employ a large number of storage devices, such as disk drives, that are accessible by one or more host processors or computers. Since reading and writing to disks is still a relatively slow operation, many data storage systems use a cache memory to speed up the transfer of information to/from the disks. In such systems, the host computers interact with the cache memory on all transfers to and from storage devices.
For example, if data is modified by a host computer, the modified data is written to cache memory, and later written back to disk (the latter operation often being referred to “destaging”). When the data storage system employs mirroring, the data to be destaged must be written to each mirror, however not necessarily at the same time.
Typically, a data structure is maintained to indicate which data elements in cache memory have been modified and therefore need to be written back to storage. Such data structures are sometimes referred to as “write pending data structures”. When host computers write new or modified data into the cache memory, the data structure is marked to indicate that the data elements are “write pending” data elements. When the data elements are destaged to storage by a data storage system controller, the data structure is cleared to indicate that the data elements on the storage devices now correspond to the data elements in the cache memory.
To speed up the destaging process, many data storage systems depend on using proximity data to allow destaging to store data at approximately similar locations on a disk. For example, if data writes are performed in a sequential order, which minimizes head movement, the data storage system minimizes delays introduced by head seeks.
Therefore, many data storage systems attempt to select and sort destaging disk writes to minimize seek time. The write pending data structure for indicating write-backs is often set up to allow a device controller looking to do a write-back to a device to search for localized write-backs and thus increase speed. One such write pending data structure is known as a “write tree”, where the data is arranged in a tree-like structure which is sorted by a predetermined index system, for example, cylinder number. The device controller is able to search the write tree by cylinder numbers for proximate write-backs, and thereby minimize the head movement necessary to write data to the disk volumes. As the number of logical volumes on a disk grows, however, the technique becomes much less efficient with respect to seek minimization.
Moreover, because searching the write tree in cache memory is a time-consuming operation that requires multiple accesses to find appropriate data, that is, data that is mature enough for destaging, data storage system performance tends to suffer. Using redundant logical volumes (or mirrors) only tends to make the problem more severe, since each mirror separately searches the same write tree.